/**
 * 2
 *  
 * @Author : roryrywang
 * @DateTime : 2024/8/23 18:49
 */

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return TreeNode类
     */
    int k = 0;
    int cnt = 0;

    void dfs(TreeNode *node, int x) {
        if (node == nullptr) return;
        k = max(k, x);
        dfs(node->left, 2*x);
        dfs(node->right, 2*x+1);
    }

    void createNode(TreeNode *node, int x) {
        if (2 * x <= k && node->left == nullptr) {
            node->left = new TreeNode(cnt++);
        }
        if (2 * x + 1 <= k && node->right == nullptr) {
            node->right = new TreeNode(cnt++);
        }
        if (node->left != nullptr) createNode(node->left, 2 * x);
        if (node->right != nullptr) createNode(node->right, 2 * x + 1);
    }

    TreeNode *makeCompleteTree(TreeNode *root) {
        if (root == nullptr) return nullptr;
        dfs(root, 1);
        createNode(root, 1);
        return root;
    }

    void printTree(TreeNode *root) {
        if (!root) return;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
            if (node == nullptr) {
                cout << "#" << " ";
            } else {
                cout << node->val << " ";
                q.push(node->left);
                q.push(node->right);
            }
        }
    }
};

int main() {
    Solution sl;
    sl.cnt = 4;
    TreeNode *root = new TreeNode(1, nullptr, new TreeNode(2, new TreeNode(3, nullptr, nullptr), nullptr));
    sl.makeCompleteTree(root);
    sl.printTree(root);
    return 0;
}